# 重复的子字符串： https://leetcode-cn.com/problems/repeated-substring-pattern/

# 1. 双指针直接模拟的方法，可惜效率太低了！ 540毫秒~ 击败了 5.77%的用户。
class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        """ 
            双指针解题， 直接模拟。 利用 两个指针，分别指向两个子串，从头到尾比较。 然后再后移，从头到尾比较。
            直到比较所有子串，是否相等。
        """
        length = 1
        left, right = 0, 1

        # 子串长度最多是主串的一半儿
        while length <= len(s)//2:
            # 遍历，看是否由此长度的子串组成
            while right <= len(s) -1:
                if s[left] != s[right]:
                    break
                left += 1
                right += 1
            
            # 判断当right遍历完最后一个元素，说明符合
            if right > len(s) - 1:
                return True

            # 否则子串长度再加上1
            length += 1
            # 如果length子串长度不能使 主串平均分为几个子串，那么一定不能组成
            while len(s) % length != 0:
                length += 1
                continue
            # 更新 left， right 指针位置
            left, right = 0, length
        
        # 最后执行到这里，一定是 False，不能有子串重复组成
        return False


# 2. 双指针模拟，代码优化（官方解答）
class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        for i in range(1, n // 2 + 1):
            if n % i == 0:
                if all(s[j] == s[j - i] for j in range(i, n)):
                    return True
        return False

# 3. 旋转数组解决
# 4. 字符串匹配解决问题
# 这是使用的字符串匹配，语言自带的函数。 也可以自己手写一个 BM， KMP算法~
class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        """
            变成字符串匹配的问题。 s 后面再拼接一个s。 再这个拼接后的字符串中，只要找到s串，就说明是。
            根据旋转数组， 旋转数组长度的次数变为原数组。
            举例子： "abcab"
            拼接 ： "abcabcabcabc"  
            从后往前， 依次是原来的串，旋转 1， 2， 3， 。。。length次的串。 
        """
        # 从1开始，去掉头部。头部拼接的本来就是原来的串，一定匹配，  ！= len(s) , 如果找到的匹配下标从len(s) 开始，那就是对应的 原始串了。 去掉这个。
        return (s + s).find(s, 1) != len(s)


